package 双指针.三数之和15;

import utils.Utils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        Arrays.sort(nums);

        for(int i = 0;i < nums.length;i++){
            if(i > 0 && nums[i] == nums[i-1]){
                continue;
            }

            // 找相反数
            int j = nums.length -1;
            int target = -nums[i];
            for(int k=i+1;k<nums.length;k++){
                if(k>i+1 && nums[k] == nums[k-1]){
                    continue;
                }

                while(k < j && nums[k]+nums[j] > target){
                    j--;
                }

                if(k==j){
                    continue;
                }

                int tmp = nums[i]+nums[j]+nums[k];
                if(tmp > 0){
                    break;
                }

                if(tmp == 0){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[k]);
                    list.add(nums[j]);
                    res.add(list);
                }

            }
        }


        return res;
    }

    public static void main(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};
        Utils.printIntListList(threeSum(nums));
    }
}
